;; Non-robust numeric functions
;; Copyright (C) 2022  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.numeric.max-subarray)

;; https://en.wikipedia.org/wiki/Maximum_subarray_problem#Computing_the_best_subarray's_position
(defn max-subarray
  "Return the starting index, count, and sum of the maximum subsequence of `coll`."
  [coll]
  (when-let [coll (seq coll)]
    (loop [coll coll
           current-start 0
           current-end 0
           current-sum 0
           best-start 0
           best-end 0
           best-sum ##-Inf]
      (if coll
        (let [extend-current-subarray? (> current-sum 0)
              start (if extend-current-subarray?
                      current-start
                      current-end)
              end (inc current-end)
              sum (if extend-current-subarray?
                    (+ current-sum (first coll))
                    (first coll))]
          (if (> sum best-sum)
            (recur (next coll)
                   start end sum
                   start end sum)
            (recur (next coll)
                   start end sum
                   best-start best-end best-sum)))
        [best-start (- best-end best-start) best-sum]))))
